/*
题目: 字符串排序
输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
https://leetcode.cn/problems/zi-fu-chuan-de-pai-lie-lcof/
 */
public class Offer38 {
    List<String> list = new ArrayList<> ();
    StringBuilder builder = new StringBuilder();

    Set<Integer> set = new HashSet<> (); // 避免垂直重复
    int n ;

    public String[] permutation(String s) {
        n = s.length();
        char[] title = s.toCharArray();
        Arrays.sort(title);
        backTrack(title);

        String[] src = new String[list.size()];
        for (int i = 0; i < list.size(); i++) {
            src[i] = list.get(i);
        }
        return src;
    }

    private void backTrack(char[] title) {
        if (builder.length() == n) {
            list.add(builder.toString());
            return ;
        }
        for (int i = 0; i < n; i++) {
            char ch = title[i];
            if (i > 0 && title[i] == title[i - 1] && !set.contains(i - 1))
                continue;
            if (!set.contains(i)) {
                builder.append(ch);
                set.add(i);

                backTrack(title);

                set.remove(i);
                builder.deleteCharAt(builder.length() - 1);
            }
        }
    }
}
